#include "stdio.h"
#include "stdlib.h"
#include "uthash.h"

// 数组中“存在”重复元素，且两个重复元素间的索引的差值<=k

typedef struct info {
    int key;
    int idx;
    UT_hash_handle hh;
} uthash_t;

int containsNearbyDuplicate(int* nums, int numsSize, int k){
    uthash_t *hash = NULL, *ret;
    int is_exist = 0;
    for (int i = 0; i < numsSize; i++) {
        HASH_FIND_INT(hash, &nums[i], ret);
        if (ret == NULL) {
            uthash_t *tmp = malloc(sizeof(*tmp));
            tmp->key = nums[i];
            tmp->idx = i;
            HASH_ADD_INT(hash, key, tmp);
        } else {
            if (i - ret->idx <= k) {
                is_exist = 1;
                break;
            }
            else ret->idx = i;
        }
    }

    uthash_t *next, *del = NULL;
    HASH_ITER(hh, hash, del, next) {
        HASH_DEL(hash, del);
        free(del);
    }
    return is_exist;   
}

void main(void) {
	int nums[] = {1, 2, 0, -1, 2, 1, 5, 8, 6, 5};
	int len = sizeof(nums) / sizeof(nums[0]);
	int k = 2;
	printf("数组中“存在”重复元素，且它们间隔<=%d? %s\n", \
		k, containsNearbyDuplicate(nums, len, k)? "yes":"no");
	// k = 3;	
	// printf("数组中“存在”重复元素，且它们间隔<=%d? %s\n", \
		// k, containsNearbyDuplicate(nums, len, k)? "yes":"no");
}